package com.lx.algorithm.temp;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-10-28 16:10:18
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-10-28     张李鑫                     1.0         1.0 Version
 */
public class MaxPalindrome {


    /**
     * 给定一个字符串str，返回这个字符串的最长回文子序列长度
     * 比如 ： str = “a12b3c43def2ghi1kpm”
     * 最长回文子序列是“1234321”或者“123c321”，返回长度7
     * <p>
     * <p>
     * 两个思路
     * 1:反转当前字符串 然后求当前字符串跟原来字符的最长子序列 就是回文
     * 2:普通思路选 与不选做选择 找到最长的回文
     *
     * @param args
     */
    public static void main(String[] args) {
        String str = "a12b3c43def2ghi1kpm";
        System.out.println(process(str));
        System.out.println(dp(str.toCharArray()));
    }


    public static int process(String val) {
        char[] chars = val.toCharArray();
        return process(chars, 0, chars.length - 1);
    }

    private static int process(char[] chars, int l, int r) {
        if (l == r) {
            return 1;
        }
        if (l == r - 1) {
            return chars[l] == chars[r] ? 2 : 1;
        }
        //没有l r 的最长回文子序列
        int p1 = process(chars, l + 1, r - 1);
        //没有l 的最长回文子序列
        int p2 = process(chars, l + 1, r);
        //没有r的最长回文子序列
        int p3 = process(chars, l, r - 1);
        //l r的全文子序列 只有chars[r]==chars[l]的时候才会有这样的情况出现  所以要判断一下 如果相等 就有两个子序列了 如果不相等就是0+后续
        int p4 = (chars[l] == chars[r] ? 2 : 0) + process(chars, l + 1, r - 1);
        return Math.max(Math.max(p1, p2), Math.max(p3, p4));
    }


    /**
     * 动态规划
     *            R   0 1 2 3 4 5 6 7
     *        L
     *        0       1 2 0 0 0 0 0 0
     *        1       0 1 2 0 0 0 0 0
     *        2       0 0 1 2 0 0 0 0
     *        3       0 0 0 1 2 0 0 0
     *        4       0 0 0 0 1 2 0 0
     *        5       0 0 0 0 0 1 2 0
     *        6       0 0 0 0 0 0 1 2
     *        7       0 0 0 0 0 0 0 1
     *
     * @param chars
     * @return
     */
    public static int dp(char[] chars) {
        int N = chars.length;
        int[][] dp = new int[N][N];
        for (int i = 0; i < N-1; i++) {
            dp[i][i] = 1;
            dp[i][i + 1] = chars[i] == chars[i + 1] ? 2 : 1;
        }

        for (int L = N-3; L >= 0; L--) {
            for (int R =L+2 ; R < N; R++) {
                int val = Math.max(dp[L][R - 1], dp[L + 1][R]);
                if (chars[L] == chars[R]) {
                    val = Math.max(val, 2 + dp[L + 1][R - 1]);
                }
                dp[L][R] = val;
            }
        }
        return dp[0][N - 1];
    }
}
